package pack_issue;

/**
 * @Author liangzai
 * @Description:
 */
import java.util.Arrays;
import java.util.Scanner;

public class Training {
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int V = scanner.nextInt();
        int[] wigth = new int[n];
        int[] val = new int[n];
        for (int i = 0; i < n; i++) {
            wigth[i] = scanner.nextInt();
            val[i] = scanner.nextInt();
        }
        int[][] dp = new int[n+1][V+1];
        int[][] dp2 = new int[n+1][V+1];
        for (int i = 0; i <= V; i++) {

        }
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if(wigth[i-1]<=j) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-wigth[i-1]]+val[i-1]);
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        System.out.println(max);
        for (int i = 0; i <= V; i++) {
            dp2[0][i] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp2[i][j] = dp2[i-1][j];
                if(wigth[i-1]<=j && dp2[i-1][j-wigth[i-1]]!=-1) {
                    dp2[i][j] = Math.max(dp2[i][j],dp[i-1][j-wigth[i-1]]+val[i-1]);
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        System.out.println(max);
    }

    //01背包问题
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int V = scanner.nextInt();
        int[][] dp = new int[n+1][V+1];
        int[] wight = new int[n+1];
        int[] val = new int[n+1];
        for (int i = 1; i <= n; i++) {
            wight[i] = scanner.nextInt();
            val[i] = scanner.nextInt();
        }
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=wight[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-wight[i]]+val[i]);
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        System.out.println(max);
        max = Integer.MIN_VALUE;
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], 0);
        }
        for (int i = 1; i <= V; i++) {
            dp[0][i] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=wight[i] && dp[i-1][j-wight[i]] != -1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-wight[i]]+val[i]);
                }
                max = Math.max(max, dp[i][V]);
            }
        }
        System.out.println(max==-1?0:max);
    }

    //分割等和子集
    public boolean canPartition1(int[] nums) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length-1;
        int sumleft = nums[left];
        int sumright = nums[right];
        while(left<right) {
            if(sumleft>sumright) {
                sumright += nums[--right];
            }else if(sumleft<sumright) {
                sumleft += nums[++left];
            }else {
                if(right-left==1) {
                    return true;
                }else {
                    sumleft += nums[++left];
                    sumright += nums[--right];
                }
            }
        }

        return false;
    }

    public boolean canPartition2(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum%2==1) return false;
        int flag = sum/2;
        int n = nums.length;
        int[][] dp = new int[n+1][flag+1];
        for (int i = 1; i <= flag; i++) {
            dp[0][i] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= flag; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=nums[i-1] && dp[i-1][j-nums[i-1]]!=-1) {
                    dp[i][j] = dp[i-1][j-nums[i-1]] + nums[i-1];
                }
            }
            if(dp[i][flag]==flag) {
                return true;
            }
        }
        return false;
    }

    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum%2==1) {
            return false;
        }
        int flag = sum/2;
        boolean[][] dp = new boolean[n+1][flag+1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= flag; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=nums[i-1]) {
                    dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][flag];
    }

    //目标和
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if((target+sum)%2==1 || (target+sum)<0) {
            return 0;
        }
        int key = (target+sum)/2;
        int[][] dp = new int[n+1][key+1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= key; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=nums[i-1]) {
                    dp[i][j] += dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][key];
    }
}














